import x10.util.Timer;
import x10.util.concurrent.AtomicInteger;

// Author: Jiabin Hu (jh3240)
// Speedup: 224.31
public class OptHisto extends BaseHisto
{
    // Fill in 'hist' with the data from 'input'
    //
    def histogram(hist: Array[int]{rank==2}, input: Array[int]{rank==1})
    {
        // Zero out the histogram
    	
    	val numAsyncs = 24;
    	val numHistAsyncs = 8;
   	
    	val maxWidth = hist.region.max(WIDTH_AXIS);
    	val maxHeight = hist.region.max(HEIGHT_AXIS);
    	val onePlusWidth = maxWidth + 1;
    	
    	val chunkSize = input.size / numAsyncs;
    	
    	val histChunkSize = onePlusWidth / numHistAsyncs;
    	
    	//var start:Long, end:Long;
    	
    	if (onePlusWidth < 1024)
    	{
    		// val tempHist:Array[AtomicInteger] = new Array[AtomicInteger](hist.region);
    		// // Little could be done here. Takes 53ms at most.
    		// //start = Timer.milliTime();
    		// finish for (k in 0..(numHistAsyncs - 1))
    		// 	async for(i in (k * histChunkSize)..((k == (numHistAsyncs - 1)) ? (onePlusWidth - 1) :(k + 1) * histChunkSize - 1))
    		// 		for (j in 0..maxWidth)
    		// 			tempHist(i, j) = new AtomicInteger(0);
    		//end = Timer.milliTime();
    		
    		//Console.OUT.println("Zeroing hist takes " + (end - start) + "ms.");

    		val tempHist:Array[Array[Int]] = new Array[Array[Int]](numAsyncs);

    		//start = Timer.milliTime();
    		//var count:AtomicInteger = new AtomicInteger(0);
    		// Fill the histogram 
    		finish
    		{
    			for (k in 0..(numAsyncs - 1))
    				async
    				{
    				    tempHist(k) = new Array[Int](hist.region, 0);
    				    val thisHist = tempHist(k);
	    				//Console.OUT.println((k * chunkSize) + " to " + ((k + 1) * chunkSize - 1));
	    				for (i in (k * chunkSize)..((k == (numAsyncs - 1)) ? (input.size - 1) :(k + 1) * chunkSize - 1))
	    				{
	    					val value: int = input(i);
	    					val y: Int = (value / (onePlusWidth)) & maxHeight;
	    					val x: Int = (value & maxWidth);
	    					
	    					thisHist(y, x) += 1;
	    					//count.incrementAndGet();
	    				}
    				}

    		}
    		//end = Timer.milliTime();
    		//Console.OUT.println(count.get());
    		//Console.OUT.println("Filling hist takes " + (end - start) + "ms.");
    		
    		//start = Timer.milliTime();
    		finish for (k in 0..(numHistAsyncs - 1))
    			async for(i in (k * histChunkSize)..((k == (numHistAsyncs - 1)) ? (onePlusWidth - 1) :(k + 1) * histChunkSize - 1))
    				for (j in 0..maxWidth)
    				{
    					hist(i, j) = 0;
    					for (n in 0..(numAsyncs - 1))
    						hist(i, j) += tempHist(n)(i, j);
    				}
    					
    		//end = Timer.milliTime();
    		//Console.OUT.println("Moving hist takes " + (end - start) + "ms.");
    	}
    	else
    	{
    		val altNumAsyncs = 8;
    		val altChunkSize = onePlusWidth / altNumAsyncs;
    		
    		//var start:Long, end:Long;
    		
    		//start = Timer.milliTime();
    		finish for (k in 0..(altNumAsyncs - 1))
    		async for (i in (k * altChunkSize)..((k == (altNumAsyncs - 1)) ? (onePlusWidth - 1) : (k + 1) * altChunkSize - 1))
    			for (j in 0..maxWidth)
    				hist(i, j) = 0;
    		//end = Timer.milliTime();
    		//Console.OUT.println("Zeroing hist takes " + (end - start) + "ms.");

    		//start = Timer.milliTime();
			for (i in 0..(input.size - 1))
			{
				val value: int = input(i);
				val y: Int = (value / (onePlusWidth)) & maxHeight;
				val x: Int = (value & maxWidth);
				
				hist(y, x) += 1;
				//count.incrementAndGet();
			}
			//end = Timer.milliTime();
			//Console.OUT.println("Filling hist takes " + (end - start) + "ms.");
    	}
    }

    public def getName() : String
    {
        return "Optimized Histogram";
    }
}
